Date: Tue, 10 Dec 1996 22:04:37 GMT
Server: NCSA/1.4.2
Content-type: text/html
Last-modified: Mon, 29 Jul 1996 17:15:45 GMT
Content-length: 1515

<HTML>

<HEAD>
<TITLE>Experimental Analysis of Treecodes</TITLE>
</HEAD>

<body bgcolor="#ffffff" text="#000070" vlink="#000000" link="#000000">

<H1>
<!WA0><A HREF="http://www.cs.washington.edu/homes/sds/papers/quals.ps">
Experimental Analysis of Treecodes for Astronomical Simulations</A>
</H1><BR>

</BODY>
 The introduction of hierarchical tree data-structures to solve the
  <I>N</I>-body problem have led to a host of algorithms with asymptotic
  complexities ranging from O(<I>n</I> log  <I>n</I>) to 
 O(<I>n</I>). Although the asymptotic complexity of different
<I>treecodes</I> are
  competitive, the constant factors between the algorithms
  have a significant impact on the CPU time. In this paper
  we examine the performance of a class of treecodes to compare the
  effectiveness of different tree structures for <I>N</I>-body simulation.
  We investigate the performance of these treecodes in both the serial
  and parallel cases.
<p> 
<HR>
This work is in 
connection with a project on 
<!WA1><A HREF="http://www.cs.washington.edu/homes/anderson/research.html">
data structures</A> by Prof. 
<!WA2><A HREF="http://www.cs.washington.edu/homes/anderson">Richard Anderson</A>.  
A <!WA3><A HREF="http://www.cs.washington.edu/homes/anderson/papers/tree.ps">draft
paper</A> is also available.
<P>
I have also put together a simple applet that animates an 
<!WA4><A HREF="http://www.cs.washington.edu/homes/sds/nbody.html" <I>N</I>-body simulation</A>.
<HR>

<ADDRESS>
<!WA5><A HREF="mailto:sds@cs.washington.edu">Sean David Sandys &lt;sds@cs.washington.e
du&gt;</A> <P>
Last revised: April 4, 1995
</ADDRESS>

</HTML>
